Qu'est-ce que tri insertion ?

Le tri par insertion est un algorithme de tri simple et efficace dans lequel chaque élément dans une liste est inséré dans sa position correcte dans une même liste triée existante.

Pour commencer, le premier élément de la liste est considéré comme trié. Ensuite, pour chaque élément suivant, il est comparé avec tous les éléments déjà triés et inséré à sa place correcte. Cette opération est répétée jusqu'à ce que la liste soit entièrement triée.

Le tri par insertion a une complexité temporelle moyenne de O(n^2), ce qui le rend efficace pour trier de petites listes, mais pas recommandé pour trier de grandes listes. Cependant, il est assez facile à comprendre et à mettre en œuvre, et peut être utilisé comme un sous-algorithme dans d'autres algorithmes de tri plus complexes.